package com.year_23.may;

/**
 * @author: jsh
 * @create: 2023/5/4 20:54
 * @Description:        2106 摘水果
 * @FileName: Day4
 * @History:
 * @自定义内容：
 */
public class Day4 {
    public static void main(String[] args) {

    }
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int res = 0;
        int length = fruits.length;
        int[] sum = new int[length+1];
        int[] indeces = new int[length];
        for (int i = 0; i < length; i++) {
            sum[i + 1] = sum[i] + fruits[i][1];
            indeces[i] = fruits[i][0];
        }
        for (int i = 0; i <= k/2; i++) {
            //先向左 i 步， 再向有移动 k - i 步
            int left = startPos - i;
            int right = startPos + k - 2*i;
            int start = lowerLimit(indeces, 0, length -1, left);
            int end = upperLimit(indeces, 0, length -1, right);
            res = Math.max(res, sum[end] - sum[start]);

            left = startPos - k + 2*i;
            right = startPos + i;
            start = lowerLimit(indeces, 0, length -1, left);
            end = upperLimit(indeces, 0, length -1, right);
            res = Math.max(res, sum[end] - sum[start]);

        }
        return res;
    }

    public static int lowerLimit(int[] arr, int left, int right, int val){
        int res = right + 1;
        while (left <= right){
            int mid = left + (right - left) /2;
            if (arr[mid] >= val){
                res = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return res;
    }

    //
    public static int upperLimit(int[] arr, int left, int right, int val){
        int res = right +1;
        while (left <= right){
            int mid = left + (right - left) /2;
            if (arr[mid] > val){
                res = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return res;
    }

}



